package leetcode.Hot100;

import java.util.Arrays;

/**
 * @author Cheng Jun
 * Description: 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
 * <p>
 * 给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。
 * <p>
 * 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/perfect-squares
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @version 1.0
 * @date 2021/11/25 13:39
 * 输入：n = 12
 * 输出：3
 * 1 <= n <= 10^4
 */
public class numSquares {
    public static void main(String[] args) {
        System.out.println(numSquares(17));
        System.out.println(numSquares1(17));
    }

    // 这题和零钱兑换很像
    static int numSquares(int n) {
        int pow = (int) Math.pow(19, 0.5);
        int[] ints = new int[pow];
        for (int i = 1; i <= pow; i++) {
            ints[i - 1] = (int) Math.pow(i, 2);
        }
        return coinChange1.coinChange(ints, n);
    }

    // 动态规划状态定义：dp[i] 表示 i 完全平方数的最少数量。 dp[n] 即为所求
    // 动态规划初始值：dp[0] = 0，注意这里 dp[0]其实是没有意义的，
    // 只是为了当n为 某个数的平方时，dp[n]可以为1，比如 4 是2的平方，所以4的完全平方数的最少数量为1
    // 动态规划转移方程 dp[i] = min{dp[i], (1 + dp[i -j*j])} , 1<=j^2<=n
    static int numSquares1(int n) {
        int[] dp = new int[n + 1];
        // 技巧性地初始化所有值为 MAX_VALUE
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], 1 + dp[i - j * j]);
            }
        }
        return dp[n];
    }

    // 数学定理:四平方和定理 证明了任意一个正整数都可以被表示为至多四个正整数的平方和。这给出了本题的答案的上界。
    // 暂不做要求
    int numSquares2(int n) {
        if (isPerfectSquare(n)) {
            return 1;
        }
        if (checkAnswer4(n)) {
            return 4;
        }
        for (int i = 1; i * i <= n; i++) {
            int j = n - i * i;
            if (isPerfectSquare(j)) {
                return 2;
            }
        }
        return 3;
    }

    // 判断是否为完全平方数
    public boolean isPerfectSquare(int x) {
        int y = (int) Math.sqrt(x);
        return y * y == x;
    }

    // 判断是否能表示为 4^k*(8m+7)
    public boolean checkAnswer4(int x) {
        while (x % 4 == 0) {
            x /= 4;
        }
        return x % 8 == 7;
    }
}
